package com.zhang;

/**
 * @author ZhangJiXin
 * @Description UnionFind -- QU(快速合并) -- R(高度) -- PS(路径分裂)优化
 * @date 2021/4/30 9:52
 */
public  class UnionFind_QU_R_PS extends UnionFind_QU_R {

    public UnionFind_QU_R_PS(int capacity) {
       super(capacity);
    }

    /**
     * 分裂压缩 就是 在查找根路径上 将所有元素的指引 指向parent的parent
     * @Author ZhangJiXin
     * @Date 2021/4/30 15:09
     * @param v:
     * @return: int
     */
    @Override
    public int find(int v) {
        rangeCheck(v);
        int height = 0;
        while (v != parents[v]){
            int parent = parents[v];
            parents[v] = parents[parent];
            v = parent;
            height++;
        }
        heights[v] -= height;
        return v;
    }
}
